<?php

namespace Tools\AlgorithmDesign;

final class Sort
{
    public static function generateInput(int $length): array
    {
        $result = [];

        for ($i = 0; $i < $length; $i++) {
            $result[] = mt_rand(0, $length * 10);
        }

        return $result;
    }

    public static function swap(&$value, &$other)
    {
        $value += $other;
        $other = $value - $other;
        $value -= $other;

        /*
        $value ^= $other;
        $other ^= $value;
        $value ^= $other;
        */
    }

    public static function sortedMerge($left, $right): array
    {
        $result = [];

        while (count($left) > 0 && count($right) > 0) {
            if ($left[0] > $right[0]) {
                $result[] = array_shift($right);
            } else {
                $result[] = array_shift($left);
            }
        }

        while (count($left) > 0) {
            $result[] = array_shift($left);
        }

        while (count($right) > 0) {
            $result[] = array_shift($right);
        }

        return $result;
    }

    public static function bubbleSort(array $input): array
    {
        $length = count($input);

        for ($i = 0; $i < $length; $i++) {
            for ($j = $i + 1; $j < $length; $j++) {
                if ($input[$i] > $input[$j]) {
                    self::swap($input[$i], $input[$j]);
                }
            }
        }

        return $input;
    }

    public static function selectionSort(array $input): array
    {
        $length = count($input);

        for ($i = 0; $i < $length; $i++) {
            $minimumIndex = $i;
            for ($j = $i + 1; $j < $length; $j++) {
                if ($input[$minimumIndex] > $input[$j]) {
                    $minimumIndex = $j;
                }
            }

            if ($minimumIndex != $i) {
                self::swap($input[$minimumIndex], $input[$i]);
            }
        }

        return $input;
    }

    public static function insertionSort(array $input): array
    {
        $length = count($input);

        for ($i = 1; $i < $length; $i++) {
            $previousIndex = $i - 1;
            $current = $input[$i];

            while ($previousIndex >= 0 && $input[$previousIndex] > $current) {
                $input[$previousIndex + 1] = $input[$previousIndex];
                $previousIndex--;
            }

            $input[$previousIndex + 1] = $current;
        }

        return $input;
    }

    public static function shellSort(array $input): array
    {
        $length = count($input);

        $gap = 1;
        while ($gap < $length / 3) {
            $gap = $gap * 3 + 1;
        }

        for (; $gap > 0; $gap = floor($gap / 3)) {
            for ($i = $gap; $i < $length; $i++) {
                $temporary = $input[$i];

                for ($j = $i - $gap; $j >= 0 && $input[$j] > $temporary; $j -= $gap) {
                    $input[$j + $gap] = $input[$j];
                }
                $input[$j + $gap] = $temporary;
            }
        }

        return $input;
    }

    public static function mergeSort(array $input): array
    {
        $length = count($input);
        if ($length < 2) {
            return $input;
        }

        $middle = floor($length / 2);

        $left = array_slice($input, 0, $middle);
        $right = array_slice($input, $middle);

        return self::sortedMerge(self::mergeSort($left), self::mergeSort($right));
    }

    public static function quickSort(array $input): array
    {
        $length = count($input);
        if ($length < 2) {
            return $input;
        }

        $middle = $input[0];
        $left = [];
        $right = [];

        for ($i = 1; $i < $length; $i++) {
            if ($input[$i] > $middle) {
                $right[] = $input[$i];
            } else {
                $left[] = $input[$i];
            }
        }

        $left = self::quickSort($left);
        $left[] = $middle;
        $right = self::quickSort($right);

        return array_merge($left, $right);
    }

    public static function countingSort(array $input, $maximum = null): array
    {
        $length = count($input);
        $sortedIndex = 0;

        if (is_null($maximum)) {
            $maximum = max($input);
        }

        $bucket = array_fill(0, $maximum, null);

        for ($i = 0; $i < $length; $i++) {
            if (!array_key_exists($input[$i], $bucket)) {
                $bucket[$input[$i]] = 0;
            }

            $bucket[$input[$i]]++;
        }

        foreach ($bucket as $key => $length) {
            if (is_null($length)) {
                continue;
            }

            for ($i = 0; $i < $length; $i++) {
                $input[$sortedIndex++] = $key;
            }
        }

        return $input;
    }

    public static function bucketSort(array $input, $bucketSize = 5): array
    {
        if (($length = count($input)) === 0) {
            return $input;
        }

        $minimum = $input[0];
        $maximum = $input[0];
        for ($i = 1; $i < $length; $i++) {
            if ($input[$i] < $minimum) {
                $minimum = $input[$i];
            } else if ($input[$i] > $maximum) {
                $maximum = $input[$i];
            }
        }

        $bucketCount = floor(($maximum - $minimum) / $bucketSize) + 1;
        $buckets = array_fill(0, $bucketCount, []);
        $result = [];

        for ($i = 0; $i < $length; $i++) {
            $buckets[floor(($input[$i] - $minimum) / $bucketSize)][] = $input[$i];
        }

        for ($i = 0; $i < $bucketCount; $i++) {
            sort($buckets[$i]);
            $currentBucketLength = count($buckets[$i]);

            for ($j = 0; $j < $currentBucketLength; $j++) {
                $result[] = $buckets[$i][$j];
            }
        }

        return $result;
    }

    public static function radixSort(array $input, $maxlength = null): array
    {
        if ($maxlength === null) {
            $maxlength = strlen((string)max($input));
        }

        $length = count($input);

        for ($i = 0; $i < $maxlength; $i++) {
            $counter = [];

            for ($j = 0; $j < $length; $j++) {
                preg_match_all('/\d/', (string)$input[$j], $matches);
                $temporary = $matches[0];
                $temporaryLength = count($temporary);

                $bucket = array_key_exists($temporaryLength - $i - 1, $temporary)
                    ? intval($temporary[$temporaryLength - $i - 1])
                    : 0;

                if (!array_key_exists($bucket, $counter)) {
                    $counter[$bucket] = [];
                }
                $counter[$bucket][] = $input[$j];
            }

            $position = 0;
            for ($j = 0; $j < 10; $j++) {
                $value = null;
                if ($counter[$j] !== null) {
                    while (($value = array_shift($counter[$j])) !== null) {
                        $input[$position++] = $value;
                    }
                }
            }
        }

        return $input;
    }

    public static function heapSort(array $input): array
    {
        $length = count($input);

        $minHeap = new \SplMinHeap();

        foreach ($input as $value) {
            $minHeap->insert($value);
        }

        for ($i = 0; $i < $length; $i++) {
            $input[$i] = $minHeap->extract();
        }

        return $input;
    }
}